/*=========================================================================================
   This file is a part of a virtual machine for the Dao programming language.
   Copyright (C) 2006-2010, Fu Limin. Email: fu@daovm.net, limin.fu@yahoo.com

   This software is free software; you can redistribute it and/or modify it under the terms 
   of the GNU Lesser General Public License as published by the Free Software Foundation; 
   either version 2.1 of the License, or (at your option) any later version.

   This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; 
   without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
   See the GNU Lesser General Public License for more details.
=========================================================================================*/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>

#include"daoString.h"
#include"daoThread.h"

#ifdef DAO_WITH_THREAD
DMutex  mutex_string_sharing;
#endif

static void DaoMBS_Resize( DaoMBS *self, size_t size )
{
  size_t i;
  if( size == self->size && self->bufSize>0 ) return;

  if( size >= self->bufSize || size < self->bufSize /2 ){
    self->bufSize = size + 1;
    self->data = (char*)dao_realloc( self->data, (self->bufSize+1)*sizeof(char) );
  }

  for(i=self->size; i<size; i++ ) self->data[i] = ' ';
  self->data[ size ] = 0;

  self->size = size;
}

int daoCountMBS = 0;

static DaoMBS* DaoMBS_New()
{
#ifdef DAO_GC_PROF
  daoCountMBS ++;
#endif
  DaoMBS *self = (DaoMBS*)dao_malloc( sizeof(DaoMBS) );
  self->refCount = 0;
  self->size = self->bufSize = 0;
  self->data = NULL;
  DaoMBS_Resize( self, 0 );
  return self;
}

static void DaoMBS_Copy( DaoMBS *self, DaoMBS *mbs )
{
  DaoMBS_Resize( self, mbs->size );
  memcpy( self->data, mbs->data, self->size * sizeof(char) );
}

static void DaoMBS_Delete( DaoMBS *self )
{
#ifdef DAO_GC_PROF
  daoCountMBS --;
#endif
  dao_free( self->data );
  dao_free( self );
}

static void DaoMBS_TryDelete( DaoMBS *self )
{
  if( self->refCount ){
#ifdef DAO_WITH_THREAD
    DMutex_Lock( & mutex_string_sharing );
#endif
    if( self->refCount ) self->refCount --;
#ifdef DAO_WITH_THREAD
    DMutex_Unlock( & mutex_string_sharing );
#endif
  }
  if( self->refCount == 0 ) DaoMBS_Delete( self );
}
static DaoMBS* DaoMBS_Refresh( DaoMBS *self )
{
  if( self->refCount >1 ){
    DaoMBS *mbs = self;
#ifdef DAO_WITH_THREAD
    DMutex_Lock( & mutex_string_sharing );
#endif
    if( self->refCount >1 ){
      self->refCount --;
      mbs = DaoMBS_New();
      mbs->refCount ++;
      DaoMBS_Copy( mbs, self );
    }
#ifdef DAO_WITH_THREAD
    DMutex_Unlock( & mutex_string_sharing );
#endif
    return mbs;
  }
  return self;
}
static void DaoMBS_Erase( DaoMBS *self, size_t start, size_t n )
{
  size_t i, rest;
  if( n > self->size-start ) n = self->size-start;
  rest = self->size - start - n;

  for( i=start; i<start+rest; i++ ) self->data[i] = self->data[i+n];
  self->data[start+rest] = 0;

  self->size -= n;
  if( self->size < 0.5*self->bufSize && self->size + 5 < self->bufSize ){
    self->bufSize = (size_t)(0.6 * self->bufSize) + 1;
    self->data = (char*)dao_realloc( self->data, (self->bufSize+1)*sizeof(char) );
  }
}
static void DaoMBS_InsertExt( DaoMBS *self, const char* chs, size_t at, size_t rm, size_t cp )
{
  size_t i;
  if( chs == NULL ) return;
  if( at > self->size ) at = self->size;
  if( rm + at > self->size ) rm = self->size - at;
  if( self->size+cp-rm + 1 > self->bufSize ){
    self->bufSize += self->bufSize/5 + cp-rm + 5;
    self->data = (char*)dao_realloc( self->data, (self->bufSize+1)*sizeof(char) );
  }
  if( cp < rm ){
    for( i=at+cp; i<self->size+cp-rm; i++ )
      self->data[i] = self->data[i+rm-cp];
  }else if( cp > rm ){
    for( i=self->size+cp-rm-1; i>=at+cp; i-- )
      self->data[i] = self->data[i+rm-cp];
  }
  for( i=0; i<cp; i++ ) self->data[i+at] = chs[i];
  self->size += cp-rm;
  self->data[self->size] = 0;
}
static void DaoMBS_InsertMBS( DaoMBS *self, const char* chs, size_t at, size_t rm )
{
  DaoMBS_InsertExt( self, chs, at, rm, strlen( chs ) );
}
static void DaoMBS_Insert( DaoMBS *self, DaoMBS *chs, size_t at, size_t rm )
{
  DaoMBS_InsertExt( self, chs->data, at, rm, chs->size );
}
static size_t DaoMBS_Find( DaoMBS *self, const char *chs, size_t start )
{
  const size_t len = (size_t)strlen( chs );
  size_t i, j;

  if( len == 0 ) return MAXSIZE;
  if( len+start > self->size ) return MAXSIZE;
  for( i=start; i<self->size-len+1; i++){
    int found = 1;
    for( j=0; j<len; j++ ){
      if( self->data[i+j] != chs[j] ){
        found = 0;
        break;
      }
    }
    if( found ) return i;
  }
  return MAXSIZE;
}
static size_t  DaoMBS_RFind( DaoMBS *self, const char* chs, size_t start )
{
  size_t len = strlen( chs );
  size_t i, j;

  if( len == 0 ) return MAXSIZE;
  if( self->size==0 ) return MAXSIZE;
  if( start <0 || start >= self->size ) start = self->size-1;
  if( len > start || len > self->size ) return MAXSIZE;
  for( i=start; i>=len; i--){
    int found = 1;
    for( j=0; j<len; j++ ){
      if( self->data[i-j] != chs[len-1-j] ){
        found = 0;
        break;
      }
    }
    if( found ) return i;
  }
  return MAXSIZE;
}
void DaoMBS_AppendChar( DaoMBS *self, const char ch )
{
  if( self->size+1 >= self->bufSize ){
    self->bufSize += self->bufSize/5 + 5;
    self->data = (char*)dao_realloc( self->data, (self->bufSize+1)*sizeof(char) );
  }
  self->data[ self->size ] = ch;
  self->size ++;
  self->data[ self->size ] = 0;
}
static void DaoMBS_AppendString( DaoMBS *self, const char *chs )
{
  size_t i;
  size_t len = strlen( chs );

  if( self->size + len + 1 >= self->bufSize ){
    self->bufSize += self->bufSize/5 + len + 5;
    self->data = (char*)dao_realloc( self->data, (self->bufSize+1)*sizeof(char) );
  }
  for( i=0; i<len + 1; i++ ) self->data[self->size+i] = chs[i];
  self->size += len;
}
static void DaoMBS_AppendMBS( DaoMBS *self, DaoMBS *chs )
{
  size_t i;
  size_t old = self->size;

  DaoMBS_Resize( self, self->size + chs->size );
  for( i=old; i<self->size; i++ ) self->data[i] = chs->data[i-old];
}
static int DaoMBS_SetWCS_C( DaoMBS *self, const wchar_t *wcs )
{
  size_t smin, len = 6 * wcslen( wcs );
  mbstate_t state;
  DaoMBS_Resize( self, len );
  memset( & state, '\0', sizeof (state) );
  smin = wcsrtombs( self->data, & wcs, len, & state );
  if( smin == (size_t)-1 ) return 0;
  DaoMBS_Resize( self, smin );
  return 1;
}
static int DaoMBS_SetWCS( DaoMBS *self, DaoWCS *wcs )
{
  size_t i;
  DaoMBS *mbs = DaoMBS_New();
  i = 0;
  while( i < wcs->size ){
    if( ! DaoMBS_SetWCS_C( mbs, wcs->data + i ) ){
      DaoMBS_Delete( mbs );
      return 0;
    }
    DaoMBS_AppendMBS( self, mbs );
    i += wcslen( wcs->data + i ) +1;
    if( i < wcs->size ) DaoMBS_AppendChar( self, '\0' );
  }
  DaoMBS_Delete( mbs );
  return 1;
}
static int DaoMBS_Compare( DaoMBS *self, DaoMBS *chs )
{
  size_t min = self->size > chs->size ? chs->size : self->size;
  char *p1 = self->data;
  char *p2 = chs->data;
  char *stop = p1 + min;
  while( p1 != stop ){
    if( *p1 == *p2 ){
      p1 ++;
      p2 ++;
    }else if( *p1 > *p2 ){
      return 1;
    }else{
      return -1;
    }
  }
  if( self->size == chs->size )
    return 0;
  else if( self->size < chs->size )
    return -1;
  return 1;
}

/**/
static void DaoWCS_Resize( DaoWCS *self, size_t size )
{
  size_t i;
  if( size == self->size && self->bufSize>0 ) return;
  if( size >= self->bufSize || size < self->bufSize /2 ){
    self->bufSize = size+1;
    self->data = (wchar_t*)dao_realloc( self->data, (self->bufSize+1)*sizeof(wchar_t) );
  }

  for(i=self->size; i<size; i++ ) self->data[i] = ' ';
  self->data[ size ] = 0;

  self->size = size;
}

static DaoWCS* DaoWCS_New()
{
  DaoWCS *self = (DaoWCS*)dao_malloc( sizeof(DaoWCS) );
  self->refCount = 0;
  self->size = self->bufSize = 0;
  self->data = NULL;
  DaoWCS_Resize( self, 0 );
  return self;
}

static void DaoWCS_Copy( DaoWCS *self, DaoWCS *wcs )
{
  DaoWCS_Resize( self, wcs->size );
  memcpy( self->data, wcs->data, self->size * sizeof(wchar_t) );
}

static void DaoWCS_Delete( DaoWCS *self )
{
  dao_free( self->data );
  dao_free( self );
}

static void DaoWCS_TryDelete( DaoWCS *self )
{
  if( self->refCount ){
#ifdef DAO_WITH_THREAD
    DMutex_Lock( & mutex_string_sharing );
#endif
    if( self->refCount ) self->refCount --;
#ifdef DAO_WITH_THREAD
    DMutex_Unlock( & mutex_string_sharing );
#endif
  }
  if( self->refCount == 0 ) DaoWCS_Delete( self );
}
static DaoWCS* DaoWCS_Refresh( DaoWCS *self )
{
  if( self->refCount>1 ){
    DaoWCS *wcs = self;
#ifdef DAO_WITH_THREAD
    DMutex_Lock( & mutex_string_sharing );
#endif
    if( self->refCount ){
      self->refCount --;
      wcs = DaoWCS_New();
      wcs->refCount ++;
      DaoWCS_Copy( wcs, self );
    }
#ifdef DAO_WITH_THREAD
    DMutex_Unlock( & mutex_string_sharing );
#endif
    return wcs;
  }
  return self;
}
static void DaoWCS_Erase( DaoWCS *self, size_t start, size_t n )
{
  size_t i, rest;
  if( n > self->size-start ) n = self->size-start;
  rest = self->size - start - n;

  for( i=start; i<start+rest; i++ ) self->data[i] = self->data[i+n];
  self->data[start+rest] = 0;

  self->size -= n;
  if( self->size < 0.5*self->bufSize && self->size + 5 < self->bufSize ){
    self->bufSize = (size_t)(0.6 * self->bufSize) + 1;
    self->data = (wchar_t*)dao_realloc( self->data, (self->bufSize+1)*sizeof(wchar_t) );
  }
}
static void DaoWCS_InsertExt( DaoWCS *self, const wchar_t* chs, size_t at, size_t rm, size_t cp )
{
  size_t i;
  if( chs == NULL ) return;
  if( at > self->size ) at = self->size;
  if( rm + at > self->size ) rm = self->size - at;
  if( self->size+cp-rm +1 > self->bufSize ){
    self->bufSize += self->bufSize/5 + cp-rm + 5;
    self->data = (wchar_t*)dao_realloc( self->data, (self->bufSize+1)*sizeof(wchar_t) );
  }
  if( cp < rm ){
    for( i=at+cp; i<self->size+cp-rm; i++ )
      self->data[i] = self->data[i+rm-cp];
  }else if( cp > rm ){
    for( i=self->size+cp-rm-1; i>=at+cp; i-- )
      self->data[i] = self->data[i+rm-cp];
  }
  for( i=0; i<cp; i++ ) self->data[i+at] = chs[i];
  self->size += cp-rm;
  self->data[self->size] = 0;
}
static void DaoWCS_InsertWCS( DaoWCS *self, const wchar_t* chs, size_t at, size_t rm )
{
  DaoWCS_InsertExt( self, chs, at, rm, wcslen( chs ) );
}
static void DaoWCS_Insert( DaoWCS *self, DaoWCS *chs, size_t at, size_t rm )
{
  DaoWCS_InsertExt( self, chs->data, at, rm, chs->size );
}
static size_t DaoWCS_Find( DaoWCS *self, const wchar_t *chs, size_t start )
{
  size_t i, j;
  const size_t len = wcslen( chs );

  if( len == 0 ) return MAXSIZE;
  if( len+start > self->size ) return MAXSIZE;
  for( i=start; i<self->size-len+1; i++){
    int found = 1;
    for( j=0; j<len; j++ ){
      if( self->data[i+j] != chs[j] ){
        found = 0;
        break;
      }
    }
    if( found ) return i;
  }
  return MAXSIZE;
}
static size_t DaoWCS_RFind( DaoWCS *self, const wchar_t* chs, size_t start )
{
  size_t i, j;
  size_t len = wcslen( chs );

  if( len == 0 ) return MAXSIZE;
  if( self->size==0 ) return MAXSIZE;
  if( start >= self->size ) start = self->size-1;
  if( len > start || len > self->size ) return MAXSIZE;
  for( i=start; i>=len; i--){
    int found = 1;
    for( j=0; j<len; j++ ){
      if( self->data[i-j] != chs[len-1-j] ){
        found = 0;
        break;
      }
    }
    if( found ) return i;
  }
  return MAXSIZE;
}
void DaoWCS_AppendChar( DaoWCS *self, const wchar_t ch )
{
  if( self->size + 1 >= self->bufSize ){
    self->bufSize += self->bufSize/5 + 5;
    self->data = (wchar_t*)dao_realloc( self->data, (self->bufSize+1)*sizeof(wchar_t) );
  }
  self->data[ self->size ] = ch;
  self->size ++;
  self->data[ self->size ] = 0;
}
static void DaoWCS_AppendString( DaoWCS *self, const wchar_t *chs )
{
  size_t i;
  size_t len = wcslen( chs );

  if( self->size + len + 1 > self->bufSize ){
    self->bufSize += self->bufSize/5 + len + 5;
    self->data = (wchar_t*)dao_realloc( self->data, (self->bufSize+1)*sizeof(wchar_t) );
  }
  for( i=0; i<len + 1; i++ ) self->data[self->size+i] = chs[i];
  self->size += len;
}
static void DaoWCS_AppendWCS( DaoWCS *self, DaoWCS *chs )
{
  size_t i;
  size_t old = self->size;

  DaoWCS_Resize( self, self->size + chs->size );
  for( i=old; i<self->size; i++ ) self->data[i] = chs->data[i-old];
}
static int DaoWCS_SetMBS_C( DaoWCS *self, const char *mbs )
{
  size_t smin, len = strlen( mbs );
  mbstate_t state;
  memset( & state, '\0', sizeof (state) );
  DaoWCS_Resize( self, len );
  /* under windows using MinGW, passing null output buffer,
   * will NOT cause the function to perform conversion and 
   * return the required buffer size. */
  smin = mbsrtowcs( self->data, & mbs, len, & state );
  if( smin == (size_t)-1 ) return 0;
  DaoWCS_Resize( self, smin );
  return 1;
}
static int DaoWCS_SetMBS( DaoWCS *self, DaoMBS *mbs )
{
  size_t i;
  DaoWCS *wcs = DaoWCS_New();
  i = 0;
  while( i < mbs->size ){
    if( ! DaoWCS_SetMBS_C( wcs, mbs->data + i ) ){
      DaoWCS_Delete( wcs );
      return 0;
    }
    DaoWCS_AppendWCS( self, wcs );
    i += strlen( mbs->data + i ) +1;
    if( i < mbs->size ) DaoWCS_AppendChar( self, L'\0' );
  }
  DaoWCS_Delete( wcs );
  return 1;
}
static int DaoWCS_Compare( DaoWCS *self, DaoWCS *chs )
{
  size_t min = self->size > chs->size ? chs->size : self->size;
  size_t i;
  for( i=0; i<min; i++ ){
    if( self->data[i] > chs->data[i] )
      return 1;
    else if( self->data[i] < chs->data[i] )
      return -1;
  }
  if( self->size == chs->size )
    return 0;
  else if( self->size < chs->size )
    return -1;
  return 1;
}

/**/
DString* DString_New( int mbs )
{
  DString *self = (DString*)dao_malloc( sizeof(DString) );
  self->mbs = NULL;
  self->wcs = NULL;
  if( mbs ){
    self->mbs = DaoMBS_New();
    self->mbs->refCount ++;
  }else{
    self->wcs = DaoWCS_New();
    self->wcs->refCount ++;
  }
  return self;
}

void DString_Delete( DString *self )
{
  /* refCount ==0 for no-sharing string: */
  if( self->mbs ){
    DaoMBS_TryDelete( self->mbs );
  }else{
    DaoWCS_TryDelete( self->wcs );
  }
  dao_free( self );
}
void DString_Detach( DString *self )
{
  if( self->mbs ){
    self->mbs = DaoMBS_Refresh( self->mbs );
  }else{
    self->wcs = DaoWCS_Refresh( self->wcs );
  }
}
void DString_SetSharing( DString *self, int sharing )
{
  int old = 0;
  int rc = 0;
  if( self->mbs ){
    old = self->mbs->refCount;
  }else{
    old = self->wcs->refCount;
  }
  if( old && sharing ) return;
  if( old ==0 && sharing ==0 ) return;
  DString_Detach( self );

#ifdef DAO_WITH_THREAD
  DMutex_Lock( & mutex_string_sharing );
#endif
  if( self->mbs ){
    self->mbs->refCount = sharing != 0;
  }else{
    self->wcs->refCount = sharing != 0;
  }
#ifdef DAO_WITH_THREAD
  DMutex_Unlock( & mutex_string_sharing );
#endif
}

int DString_IsMBS( DString *self )
{
  return ( self->wcs == NULL );
}
int DString_IsDigits( DString *self )
{
  size_t i;
  if( self->mbs ){
    for( i=0; i<self->mbs->size; i++ )
      if( self->mbs->data[i] < '0' || self->mbs->data[i] > '9' )
        return 0;
  }else{
    for( i=0; i<self->wcs->size; i++ )
      if( self->wcs->data[i] < L'0' || self->wcs->data[i] > L'9' )
        return 0;
  }
  return 1;
}
int DString_IsDecimal( DString *self )
{
  size_t i;
  if( self->mbs ){
    for( i=0; i<self->mbs->size; i++ )
      if( (self->mbs->data[i] < '0' || self->mbs->data[i] > '9')
        && self->mbs->data[i] != '.' )
        return 0;
  }else{
    for( i=0; i<self->wcs->size; i++ )
      if( (self->wcs->data[i] < L'0' || self->wcs->data[i] > L'9' )
        && self->mbs->data[i] != L'.' )
        return 0;
  }
  return 1;
}

char*  DString_GetMBS( DString *self )
{
  DString_ToMBS( self );
  return self->mbs->data;
}
wchar_t* DString_GetWCS( DString *self )
{
  DString_ToWCS( self );
  return self->wcs->data;
}
void DString_SetMBS( DString *self, const char *chs )
{
  if( self->mbs && self->mbs->data == chs ) return;
  DString_Clear( self );
  if( chs ) DString_AppendMBS( self, chs );
}
void DString_SetWCS( DString *self, const wchar_t *chs )
{
  if( self->wcs && self->wcs->data == chs ) return;
  DString_Clear( self );
  if( chs ) DString_AppendWCS( self, chs );
}
void DString_ToWCS( DString *self )
{
  if( self->wcs ) return;
  self->wcs = DaoWCS_New();
  /* refCount ==0 for no-sharing string: */
  if( self->mbs->refCount ) self->wcs->refCount ++;
  DaoWCS_SetMBS( self->wcs, self->mbs );
  DaoMBS_TryDelete( self->mbs );
  self->mbs = 0;
}
void DString_ToMBS( DString *self )
{
  if( self->mbs ) return;
  self->mbs = DaoMBS_New();
  /* refCount ==0 for no-sharing string: */
  if( self->wcs->refCount ) self->mbs->refCount ++;
  DaoMBS_SetWCS( self->mbs, self->wcs );
  DaoWCS_TryDelete( self->wcs );
  self->wcs = 0;
}
void DString_ToLower( DString *self )
{
  size_t i;
  if( self->mbs ){
    char *data;
    self->mbs = DaoMBS_Refresh( self->mbs );
    data = self->mbs->data;
    for( i=0; i<self->mbs->size; i++ ){
      *data = tolower( *data );
      data ++;
    }
  }else{
    wchar_t *data;
    self->wcs = DaoWCS_Refresh( self->wcs );
    data = self->wcs->data;
    for( i=0; i<self->wcs->size; i++ ){
      *data = tolower( *data );
      data ++;
    }
  }
}
void DString_ToUpper( DString *self )
{
  size_t i;
  if( self->mbs ){
    char *data;
    self->mbs = DaoMBS_Refresh( self->mbs );
    data = self->mbs->data;
    for( i=0; i<self->mbs->size; i++ ){
      *data = ( (size_t)(*data - 'a') ) < 26 ? *data = (*data) ^ 0x20 : *data;
      data ++;
    }
  }else{
    wchar_t *data;
    self->wcs = DaoWCS_Refresh( self->wcs );
    data = self->wcs->data;
    for( i=0; i<self->wcs->size; i++ ){
      *data = ( (size_t)(*data - L'a') ) < 26 ? *data = (*data) ^ 0x20 : *data;
      data ++;
    }
  }
}
size_t DString_Size( DString *self )
{
  if( self->mbs ) return self->mbs->size;
  else if( self->wcs ) return self->wcs->size;
  return 0;
}

void DString_Resize( DString *self, size_t size )
{
  if( self->mbs ){
    self->mbs = DaoMBS_Refresh( self->mbs );
    DaoMBS_Resize( self->mbs, size );
  }else{
    self->wcs = DaoWCS_Refresh( self->wcs );
    DaoWCS_Resize( self->wcs, size );
  }
}
void DString_Clear( DString *self )
{
  if( self->mbs ){
    if( self->mbs->refCount > 1 ){
#ifdef DAO_WITH_THREAD
      DMutex_Lock( & mutex_string_sharing );
#endif
      if( self->mbs->refCount > 1 ){
        self->mbs->refCount --;
        self->mbs = NULL;
      }
#ifdef DAO_WITH_THREAD
      DMutex_Unlock( & mutex_string_sharing );
#endif
    }
    if( self->mbs == NULL ){
      self->mbs = DaoMBS_New();
      self->mbs->refCount = 1;
    }else{
      DaoMBS_Resize( self->mbs, 0 );
    }
  }else{
    if( self->wcs->refCount > 1 ){
#ifdef DAO_WITH_THREAD
      DMutex_Lock( & mutex_string_sharing );
#endif
      if( self->wcs->refCount > 1 ){
        self->wcs->refCount --;
        self->wcs = NULL;
      }
#ifdef DAO_WITH_THREAD
      DMutex_Unlock( & mutex_string_sharing );
#endif
    }
    if( self->wcs == NULL ){
      self->wcs = DaoWCS_New();
      self->wcs->refCount = 1;
    }else{
      DaoWCS_Resize( self->wcs, 0 );
    }
  }
}
void DString_Erase( DString *self, size_t start, size_t n )
{
  if( self->mbs ){
    self->mbs = DaoMBS_Refresh( self->mbs );
    DaoMBS_Erase( self->mbs, start, n );
  }else{
    self->wcs = DaoWCS_Refresh( self->wcs );
    DaoWCS_Erase( self->wcs, start, n );
  }
}
void DString_Insert( DString *self, DString *chs, size_t at, size_t rm )
{
  if( self->mbs && chs->mbs ){
    self->mbs = DaoMBS_Refresh( self->mbs );
    DaoMBS_Insert( self->mbs, chs->mbs, at, rm );
  }else if( self->wcs && chs->wcs ){
    self->wcs = DaoWCS_Refresh( self->wcs );
    DaoWCS_Insert( self->wcs, chs->wcs, at, rm );
  }else if( self->mbs ){
    DaoMBS *mbs = DaoMBS_New();
    DaoMBS_SetWCS( mbs, chs->wcs );
    self->mbs = DaoMBS_Refresh( self->mbs );
    DaoMBS_Insert( self->mbs, mbs, at, rm );
    DaoMBS_Delete( mbs );
  }else{
    DaoWCS *wcs = DaoWCS_New();
    DaoWCS_SetMBS( wcs, chs->mbs );
    self->wcs = DaoWCS_Refresh( self->wcs );
    DaoWCS_Insert( self->wcs, wcs, at, rm );
    DaoWCS_Delete( wcs );
  }
}
void DString_InsertMBS( DString *self, const char *chs, size_t at, size_t rm )
{
  if( self->mbs ){
    self->mbs = DaoMBS_Refresh( self->mbs );
    DaoMBS_InsertMBS( self->mbs, chs, at, rm );
  }else{
    DaoMBS *mbs = DaoMBS_New();
    DaoWCS *wcs = DaoWCS_New();
    DaoMBS_InsertMBS( mbs, chs, 0, 0 );
    DaoWCS_SetMBS( wcs, mbs );
    self->wcs = DaoWCS_Refresh( self->wcs );
    DaoWCS_Insert( self->wcs, wcs, at, rm );
    DaoMBS_Delete( mbs );
    DaoWCS_Delete( wcs );
  }
}
void DString_InsertChar( DString *self, const char ch, size_t at )
{
  char chs[2];
  chs[0] = ch;
  chs[1] = '\0';
  DString_InsertMBS( self, chs, at, 0 );
}
void DString_InsertWCS( DString *self, const wchar_t *chs, size_t at, size_t rm )
{
  if( self->wcs ){
    self->wcs = DaoWCS_Refresh( self->wcs );
    DaoWCS_InsertWCS( self->wcs, chs, at, rm );
  }else{
    DaoMBS *mbs = DaoMBS_New();
    DaoWCS *wcs = DaoWCS_New();
    DaoWCS_InsertWCS( wcs, chs, 0, 0 );
    DaoMBS_SetWCS( mbs, wcs );
    self->mbs = DaoMBS_Refresh( self->mbs );
    DaoMBS_Insert( self->mbs, mbs, at, rm );
    DaoMBS_Delete( mbs );
    DaoWCS_Delete( wcs );
  }
}
void DString_Append( DString *self, DString *chs )
{
  if( self == NULL ) return; /* in parsing, DaoInode.annot can be NULL */
  if( self->mbs && chs->mbs ){
    self->mbs = DaoMBS_Refresh( self->mbs );
    DaoMBS_AppendMBS( self->mbs, chs->mbs );
  }else if( self->wcs && chs->wcs ){
    self->wcs = DaoWCS_Refresh( self->wcs );
    DaoWCS_AppendWCS( self->wcs, chs->wcs );
  }else if( self->mbs ){
    DString_InsertWCS( self, chs->wcs->data, self->mbs->size, 0 );
  }else{
    DString_InsertMBS( self, chs->mbs->data, self->wcs->size, 0 );
  }
}
void DString_AppendChar( DString *self, const char ch )
{
  if( self == NULL ) return; /* in parsing, DaoInode.annot can be NULL */
  if( self->mbs ){
    self->mbs = DaoMBS_Refresh( self->mbs );
    DaoMBS_AppendChar( self->mbs, ch );
  }else{
    self->wcs = DaoWCS_Refresh( self->wcs );
    DaoWCS_AppendChar( self->wcs, (const wchar_t) ch );
  }
}
void DString_AppendWChar( DString *self, const wchar_t ch )
{
  wchar_t chs[2] = { 0, 0 };
  chs[0] = ch;
  if( self->mbs ){
    self->mbs = DaoMBS_Refresh( self->mbs );
    DString_AppendWCS( self, chs );
  }else{
    self->wcs = DaoWCS_Refresh( self->wcs );
    DaoWCS_AppendChar( self->wcs, ch );
  }
}
void DString_AppendMBS( DString *self, const char *chs )
{
  if( self == NULL ) return; /* in parsing, DaoInode.annot can be NULL */
  if( self->mbs ){
    self->mbs = DaoMBS_Refresh( self->mbs );
    DaoMBS_AppendString( self->mbs, chs );
  }else{
    DString_InsertMBS( self, chs, self->wcs->size, 0 );
  }
}
void DString_AppendWCS( DString *self, const wchar_t *chs )
{
  if( self->wcs ){
    self->wcs = DaoWCS_Refresh( self->wcs );
    DaoWCS_AppendString( self->wcs, chs );
  }else{
    DString_InsertWCS( self, chs, self->mbs->size, 0 );
  }
}
void DString_AppendBytes( DString *self, const char *bytes, size_t count )
{
  size_t i, oldsize;
  char *data;

  DString_ToMBS( self );
  if( bytes ==NULL || count == 0 ) return;
  oldsize = self->mbs->size;
  DString_Resize( self, oldsize + count );
  data = self->mbs->data + oldsize;
  for( i=0; i<count; i++ ) data[i] = bytes[i];
}
void DString_SetBytes( DString *self, const char *bytes, size_t count )
{
  DString_Clear( self );
  DString_AppendBytes( self, bytes, count );
}
void DString_Replace( DString *self, DString *chs, size_t start, size_t rm )
{
  DString_Insert( self, chs, start, rm );
}
void DString_ReplaceMBS( DString *self, const char *chs, size_t start, size_t rm )
{
  /* Use by DaoParser only, guarantee to be MBS. */
  if( self->mbs ){
    self->mbs = DaoMBS_Refresh( self->mbs );
    DaoMBS_InsertMBS( self->mbs, chs, start, rm );
  }
}
void DString_Substr( DString *self, DString *sub, size_t from, size_t n )
{
  size_t i;
  if( self->wcs ) DString_ToWCS( sub );

  if( self->mbs ){
    size_t size = self->mbs->size;
    if( from >= size ){
      DString_Clear( sub );
      return;
    }
    if( n < 0 || n > size ) n = size;
    if( from+n > size ) n = size-from;
    DString_Resize( sub, n );

    for( i=0; i<n; i++) sub->mbs->data[i] = self->mbs->data[i+from];
  }else{
    size_t size = self->wcs->size;
    if( from >= size ){
      DString_Clear( sub );
      return;
    }
    if( n < 0 || n > size ) n = size;
    if( from+n > size ) n = size-from;
    DString_Resize( sub, n );

    for( i=0; i<n; i++) sub->wcs->data[i] = self->wcs->data[i+from];
  }
}
size_t DString_Find( DString *self, DString *chs, size_t start )
{
  size_t res = MAXSIZE;
  if( self->mbs && chs->mbs ){
    res = DaoMBS_Find( self->mbs, chs->mbs->data, start );
  }else if( self->wcs && chs->wcs ){
    res = DaoWCS_Find( self->wcs, chs->wcs->data, start );
  }else if( self->mbs ){
    DaoMBS *mbs = DaoMBS_New();
    DaoMBS_SetWCS( mbs, chs->wcs );
    res = DaoMBS_Find( self->mbs, mbs->data/*XXX*/, start );
    DaoMBS_Delete( mbs );
  }else{
    DaoWCS *wcs = DaoWCS_New();
    DaoWCS_SetMBS( wcs, chs->mbs );
    res = DaoWCS_Find( self->wcs, wcs->data, start );
    DaoWCS_Delete( wcs );
  }
  return res;
}
size_t DString_RFind( DString *self, DString *chs, size_t start )
{
  size_t res = MAXSIZE;
  if( self->mbs && chs->mbs ){
    res = DaoMBS_RFind( self->mbs, chs->mbs->data, start );
  }else if( self->wcs && chs->wcs ){
    res = DaoWCS_RFind( self->wcs, chs->wcs->data, start );
  }else if( self->mbs ){
    DaoMBS *mbs = DaoMBS_New();
    DaoMBS_SetWCS( mbs, chs->wcs );
    res = DaoMBS_RFind( self->mbs, mbs->data, start );
    DaoMBS_Delete( mbs );
  }else{
    DaoWCS *wcs = DaoWCS_New();
    DaoWCS_SetMBS( wcs, chs->mbs );
    res = DaoWCS_RFind( self->wcs, wcs->data, start );
    DaoWCS_Delete( wcs );
  }
  return res;
}
size_t DString_FindMBS( DString *self, const char *ch, size_t start )
{
  size_t res = MAXSIZE;
  if( self->mbs ){
    res = DaoMBS_Find( self->mbs, ch, start );
  }else{
    DaoMBS *mbs = DaoMBS_New();
    DaoMBS_SetWCS( mbs, self->wcs );
    res = DaoMBS_Find( mbs, ch, start );
    DaoMBS_Delete( mbs );
  }
  return res;
}
size_t DString_RFindMBS( DString *self, const char *ch, size_t start )
{
  size_t res = MAXSIZE;
  if( self->mbs ){
    res = DaoMBS_RFind( self->mbs, ch, start );
  }else{
    DaoMBS *mbs = DaoMBS_New();
    DaoMBS_SetWCS( mbs, self->wcs );
    res = DaoMBS_RFind( mbs, ch, start );
    DaoMBS_Delete( mbs );
  }
  return res;
}
size_t DString_FindChar( DString *self, char ch, size_t start )
{
  size_t i;
  if( self->mbs ){
    for(i=start; i<self->mbs->size; i++ )
      if( self->mbs->data[i] == ch ) return i;
  }else{
    wchar_t wch = ch;
    for(i=start; i<self->wcs->size; i++ )
      if( self->wcs->data[i] == wch ) return i;
  }
  return MAXSIZE;
}
size_t DString_RFindChar( DString *self, char ch, size_t start )
{
  int i;
  if( self->mbs ){
    if( self->mbs->size ==0 ) return MAXSIZE;
    if( start >= self->mbs->size ) start = self->mbs->size -1;
    for(i=start; i >=0; i-- )
      if( self->mbs->data[i] == ch ) return i;
  }else{
    wchar_t wch = ch;
    if( self->wcs->size ==0 ) return MAXSIZE;
    if( start >= self->wcs->size ) start = self->wcs->size -1;
    for(i=start; i >=0; i-- )
      if( self->wcs->data[i] == wch ) return i;
  }
  return MAXSIZE;
}
size_t DString_FindWChar( DString *self, wchar_t ch, size_t start )
{
  size_t i;
  if( self->wcs ){
    for(i=start; i<self->wcs->size; i++ )
      if( self->wcs->data[i] == ch ) return i;
  }else{
    DaoWCS *wcs = DaoWCS_New();
    DaoWCS_SetMBS( wcs, self->mbs );
    for(i=start; i<wcs->size; i++ )
      if( wcs->data[i] == ch ) return i;
    DaoWCS_Delete( wcs );
  }
  return MAXSIZE;
}

DString* DString_Copy( DString *self )
{
  DString *str = DString_New( self->mbs != 0 );
  DString_Assign( str, self );
  return str;
}
/* Real copying, no implicit sharing here. For thread safty. */
DString* DString_DeepCopy( DString *self )
{
  DString *copy = DString_New( DString_IsMBS( self ) );
  if( DString_IsMBS( self ) ){
    DString_Resize( copy, self->mbs->size );
    memcpy( copy->mbs->data, self->mbs->data, self->mbs->size *sizeof(char) );
  }else{
    DString_Resize( copy, self->wcs->size );
    memcpy( copy->wcs->data, self->wcs->data, self->wcs->size *sizeof(wchar_t) );
  }
  return copy;
}
void DString_Assign( DString *self, DString *chs )
{
  int rc = 0;
  int rc2 = 0;
  if( self == NULL ) return; /* in parsing, DaoInode.annot can be NULL */
  if( self == chs ) return;
  if( ( self->mbs && self->mbs == chs->mbs ) || ( self->wcs && self->wcs == chs->wcs ) ) return;

  if( self->mbs ){
    rc = self->mbs->refCount;
    if( rc ){
      DaoMBS_TryDelete( self->mbs );
      self->mbs = 0;
    }
  }else{
    rc = self->wcs->refCount;
    if( rc ){
      DaoWCS_TryDelete( self->wcs );
      self->wcs = 0;
    }
  }
  if( chs->mbs ){
    rc2 = chs->mbs->refCount;
  }else{
    rc2 = chs->wcs->refCount;
  }

  if( rc && rc2 ){
#ifdef DAO_WITH_THREAD
    DMutex_Lock( & mutex_string_sharing );
#endif
    if( chs->mbs ){
      self->mbs = chs->mbs;
      self->mbs->refCount ++;
    }else{
      self->wcs = chs->wcs;
      self->wcs->refCount ++;
    }
#ifdef DAO_WITH_THREAD
    DMutex_Unlock( & mutex_string_sharing );
#endif
  }else if( rc == 0 ){
    if( self->mbs && chs->mbs ){
      DaoMBS_Copy( self->mbs, chs->mbs );
    }else if( self->mbs && chs->wcs ){
      DaoMBS_SetWCS( self->mbs, chs->wcs );
    }else if( self->wcs && chs->mbs ){
      DaoWCS_SetMBS( self->wcs, chs->mbs );
    }else{
      DaoWCS_Copy( self->wcs, chs->wcs );
    }
  }else{
    if( chs->mbs ){
      self->mbs = DaoMBS_New();
      self->mbs->refCount = 1;
      DaoMBS_Copy( self->mbs, chs->mbs );
    }else{
      self->wcs = DaoWCS_New();
      self->wcs->refCount = 1;
      DaoWCS_Copy( self->wcs, chs->wcs );
    }
  }
}
int DString_Compare( DString *self, DString *chs )
{
  int res = 0;
  if( self->mbs && chs->mbs ){
    res = DaoMBS_Compare( self->mbs, chs->mbs );
  }else if( self->wcs && chs->wcs ){
    res = DaoWCS_Compare( self->wcs, chs->wcs );
  }else if( self->mbs ){
    DaoMBS *mbs = DaoMBS_New();
    DaoMBS_SetWCS( mbs, chs->wcs );
    res = DaoMBS_Compare( self->mbs, mbs );
    DaoMBS_Delete( mbs );
  }else{
    DaoWCS *wcs = DaoWCS_New();
    DaoWCS_SetMBS( wcs, chs->mbs );
    res = DaoWCS_Compare( self->wcs, wcs );
    DaoWCS_Delete( wcs );
  }
  return res;
}
int DString_EQ( DString *self, DString *chs )
{
  return (DString_Compare( self, chs )==0);
}
void DString_Add( DString *self, DString *left, DString *right )
{
  DString_Assign( self, left );
  DString_Append( self, right );
}
void DString_Chop( DString *self )
{
  if( self->mbs ){
    if( self->mbs->size > 0 && self->mbs->data[ self->mbs->size-1 ] == EOF ){
      self->mbs->data[ self->mbs->size-1 ] = 0;
      self->mbs->size --;
    }
    if( self->mbs->size > 0 && self->mbs->data[ self->mbs->size-1 ] == '\n' ){
      self->mbs->data[ self->mbs->size-1 ] = 0;
      self->mbs->size --;
    }
    if( self->mbs->size > 0 && self->mbs->data[ self->mbs->size-1 ] == '\r' ){
      self->mbs->data[ self->mbs->size-1 ] = 0;
      self->mbs->size --;
    }
  }else{
    if( self->wcs->size > 0 && self->wcs->data[ self->wcs->size-1 ] == EOF ){
      self->wcs->data[ self->wcs->size-1 ] = 0;
      self->wcs->size --;
    }
    if( self->wcs->size > 0 && self->wcs->data[ self->wcs->size-1 ] == L'\n' ){
      self->wcs->data[ self->wcs->size-1 ] = 0;
      self->wcs->size --;
    }
    if( self->wcs->size > 0 && self->wcs->data[ self->wcs->size-1 ] == L'\r' ){
      self->wcs->data[ self->wcs->size-1 ] = 0;
      self->wcs->size --;
    }
  }
}
void DString_Simplify( DString *self )
{
  int i, ch;
  if( self->mbs ){
    while( self->mbs->size > 0 ){
      ch = self->mbs->data[ self->mbs->size-1 ];
      if( ch == EOF || isspace( ch ) ){
        self->mbs->size --;
        self->mbs->data[ self->mbs->size ] = 0;
      }else{
        break;
      }
    }
    for( i=0; i < self->mbs->size; i++ ){
      ch = self->mbs->data[i];
      if( ch != EOF && ! isspace( ch ) ) break;
    }
    DString_Erase( self, 0, i );
  }else{
    while( self->wcs->size > 0 ){
      ch = self->wcs->data[ self->wcs->size-1 ];
      if( ch == EOF || isspace( ch ) ){
        self->wcs->size --;
        self->wcs->data[ self->wcs->size ] = 0;
      }else{
        break;
      }
    }
    for( i=0; i < self->wcs->size; i++ ){
      ch = self->wcs->data[i];
      if( ch != EOF && ! isspace( ch ) ) break;
    }
    DString_Erase( self, 0, i );
  }
}
size_t DString_BalancedChar( DString *self, uint_t ch0, uint_t lch0, uint_t rch0, 
    uint_t esc0, size_t start, size_t end, int countonly )
{
  size_t i, count = 0;
  if( self->mbs ){
    size_t size = self->mbs->size;
    char *src = self->mbs->data;
    char chr = (char) ch0;
    char lch = (char) lch0;
    char rch = (char) rch0;
    char esc = (char) esc0;
    char c;
    int bc = 0;
    if( ch0 >= 128 || start >= size ) return MAXSIZE;
    if( end > size ) end = size;
    for(i=start; i<end; i++){
      c = src[i];
      if( c == esc ){
        i ++;
        continue;
      }
      if( c == chr && bc ==0 ){
        if( countonly )
          count ++;
        else return i;
      }
      if( c == lch ){
        bc ++;
      }else if( c == rch ){
        bc --;
        if( bc <0 ) return MAXSIZE;
      }
    }
  }else{
    size_t size = self->wcs->size;
    wchar_t *src = self->wcs->data;
    wchar_t chr = (wchar_t) ch0;
    wchar_t lch = (wchar_t) lch0;
    wchar_t rch = (wchar_t) rch0;
    wchar_t esc = (wchar_t) esc0;
    wchar_t c;
    int bc = 0;
    if( ch0 >= 128 || start >= size ) return MAXSIZE;
    if( end > size ) end = size;
    for(i=start; i<end; i++){
      c = src[i];
      if( c == esc ){
        i ++;
        continue;
      }
      if( c == chr && bc ==0 ){
        if( countonly )
          count ++;
        else return i;
      }
      if( c == lch ){
        bc ++;
      }else if( c == rch ){
        bc --;
        if( bc <0 ) return MAXSIZE;
      }
    }
  }
  if( countonly ) return count;
  return MAXSIZE;
}

/* Corrected Block Tiny Encryption Algorithm (Corrected Block TEA, or XXTEA)
 * by David Wheeler and Roger Needham
 */
#define MX  ( (((z>>5)^(y<<2))+((y>>3)^(z<<4)))^((sum^y)+(k[(p&3)^e]^z)) )
   
int btea(int* v, int n, int *k)
{
  unsigned int z, y=v[0], sum=0, e, DELTA=0x9e3779b9;
  int p, q ;
  if (n > 1) { /* Coding Part */
    z=v[n-1];           
    q = 6+52/n ;
    while (q-- > 0) {
      sum += DELTA;
      e = (sum>>2) & 3 ;
      for (p=0; p<n-1; p++) y = v[p+1], z = v[p] += MX;
      y = v[0];
      z = v[n-1] += MX;
    }
    return 0 ; 
  } else if (n < -1) {  /* Decoding Part */
    n = -n ;
    q = 6+52/n ;
    sum = q*DELTA ;
    while (sum != 0) {
      e = (sum>>2) & 3;
      for (p=n-1; p>0; p--) z = v[p-1], y = v[p] -= MX;
      z = v[n-1];
      y = v[0] -= MX;
      sum -= DELTA;
    }
    return 0;
  }
  return 1;
}

const char *dec2hex = "0123456789abcdef";

static int HexDigit( char d )
{
  d = d | 0x20;
  if( ( (size_t)(d-'0') ) < 10 ) return d - '0';
  else if( ( (size_t)(d-'a') ) < 26 ) return d + 10 - 'a';
  return -1;
}
static int STR_Cipher( DString *self, DString *key, int hex, int flag )
{
  unsigned char ks[16];
  unsigned char *data = NULL;
  size_t size = 0;
  int i;
  DString_Detach( self );
  DString_ToMBS( self );
  if( self->mbs->size == 0 ) return 0;
  DString_ToMBS( key );
  if( key->mbs->size >= 32 ){
    for(i=0; i<16; i++){
      signed char c1 = HexDigit( key->mbs->data[2*i] );
      signed char c2 = HexDigit( key->mbs->data[2*i+1] );
      if( c1 <0 || c2 <0 ) return 1;
      ks[i] = 16 * c1 + c2;
    }
  }else if( key->mbs->size >= 16 ){
    memcpy( ks, key->mbs->data, 16 );
  }else{
    return 1;
  }
  if( flag == 1 ){
    size = self->mbs->size;
    i = size % 4;
    if( i ) i = 4 - i;
    DString_Resize( self, size + 4 + i );
    memmove( self->mbs->data + 4, self->mbs->data, size );
    *(int*) self->mbs->data = size;
    data = (unsigned char*) self->mbs->data;
    btea( (int*)self->mbs->data, self->mbs->size / 4, (int*) ks );
    if( hex ){
      size = self->mbs->size;
      DString_Resize( self, 2 * size );
      data = (unsigned char*) self->mbs->data;
      for(i=size-1; i>=0; i--){
        self->mbs->data[2*i+1] = dec2hex[ data[i] % 16 ];
        self->mbs->data[2*i] = dec2hex[ data[i] / 16 ];
      }
    }
  }else{
    if( hex ){
      if( self->mbs->size % 2 ) return 1;
      data = (unsigned char*) self->mbs->data;
      size = self->mbs->size / 2;
      for(i=0; i<size; i++){
        char c1 = HexDigit( data[2*i] );
        char c2 = HexDigit( data[2*i+1] );
        if( c1 <0 || c2 <0 ) return 1;
        data[i] = 16 * c1 + c2;
      }
      DString_Resize( self, size );
    }
    btea( (int*)self->mbs->data, - (self->mbs->size / 4), (int*) ks );
    size = *(int*) self->mbs->data;
    DString_Erase( self, 0, 4 );
    self->mbs->size = size;
  }
  return 0;
}
int DString_Encrypt( DString *self, DString *key, int hex )
{
  return STR_Cipher( self, key, hex, 1 );
}
int DString_Decrypt( DString *self, DString *key, int hex )
{
  return STR_Cipher( self, key, hex, 0 );
}
